package q392_isSubsequence;

public class Solution_2 {
    /*
    关于dp的解法 则需要参考1143题
    同样关于子序列 此处需要考虑的是 s的整体是否完全为t的一个子序列
    因此dp的递推公式发生了变化
    相较于s.charAt(i-1) == t.charAt(j-1)可以直接推断dp[i][j] = dp[i-1][j-1] + 1;
    else中的判断更需要思考：
    在1143题中 判断最大子序列是具有三个方向的
    而在此处我们考虑的是 s 是否为 t 的子序列
    所以这里dp[i][j] = dp[i][j-1];也就代表着 当i - 1 和 j - 1两个位置的字符没有匹配成功时
    s中前i - 1个字符与t中前j - 1个字符的匹配情况 仍然适用于 s中前i - 1个字符与t中前j - 2个字符的匹配情况
    （代表j - 1这个字符加入后并没有使得匹配变多）

    尽管我们使用1143题的求最长公共子序列的代码仍然能够解决该问题
    但是考虑到s与t的从属关系 可以减少dp的方向 提高程序的效率
     */
    public boolean isSubsequence(String s, String t) {
        int length1 = s.length(), length2 = t.length();
        int[][] dp = new int[length1 + 1][length2 + 1];

        for(int i = 1; i <= length1; i++){
            for(int j = 1; j <= length2; j++){

                if(s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
//        if(dp[length1][length2] == length1){
//            return true;
//        }else{
//            return false;
//        }
        return dp[length1][length2] == length1;
    }

}
